package 每日一题;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/pancake-sorting/
 */
public class _969_煎饼排序 {
    public List<Integer> pancakeSort(int[] arr) {
        int n = arr.length;
        List<Integer> ans = new ArrayList<>();
        for (int i = n; i > 1; i--) {
            int index = 0;
            // 遍历查找最大值的下标
            for (int j = 1; j < i; j++) {
                if (arr[j] >= arr[index]) {
                    index = j;
                }
            }
            // 如果坐标相等，则跳过此次循环
            if (index == i - 1) {
                continue;
            }
            // 反转两次将最大值放入末尾
            reverse(index, arr);
            reverse(i - 1, arr);
            // 将反转下标记录
            ans.add(index + 1);
            ans.add(i);
        }
        return ans;
    }

    /**
     * 使用双指针进行反转数组
     * @param index 从0开始到目标下标进行反转
     * @param arr 目标数组
     */
    private void reverse(int index, int[] arr) {
        int l = 0;
        for (int i = index; i > l; i--) {
            int temp = arr[l];
            arr[l++] = arr[i];
            arr[i] = temp;
        }
    }
}
